package wh.大根堆;

import java.util.Arrays;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2022/12/11 11:45
 * @description:
 * @version:
 */
public class TreeNode {
    // 从最后一个非叶子节点开始调整，调整为一个大根堆
    private static void BuildMaxHeap(int[]arr){
        if (arr == null || arr.length < 2){
            return;
        }

        for (int i = arr.length/2 - 1; i > -1; i--){
            adjustMaxHeap(arr, arr.length, i);
        }

    }

    private static void adjustMaxHeap(int[]arr, int size, int i){
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int max = i;

        if (left < size && arr[left] > arr[max]){
            max = left;
        }

        if (right < size && arr[right] > arr[max]){
            max = right;
        }

        if (max != i){
            swap(arr, i, max);
            adjustMaxHeap(arr, size, max);
        }
    }

    private static void swap(int []arr, int i, int j){
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{23,19,81,79,89,83,17,48,55,26};
        BuildMaxHeap(arr);

        System.out.println(Arrays.toString(arr));
    }
}


